package leetcode_700;

/**
 *@author 周杨
 *KInversePairsArray_629 给定一个正整数n 表示1-n的数字排列 给定k 问有多少种排列 有k个逆序对
 *describe:
 *2018年9月22日 下午3:02:36
 */
public class KInversePairsArray_629 {
	
	public static int kInversePairs(int n, int k) {
        int mod = 1000000007;
        if (k > n*(n-1)/2 || k < 0) return 0;
        if (k == 0 || k == n*(n-1)/2) return 1;
        long[][] dp = new long[n+1][k+1];
        dp[2][0] = 1;
        dp[2][1] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= Math.min(k, i*(i-1)/2); j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
                if (j >= i) dp[i][j] -= dp[i-1][j-i];
                dp[i][j] = (dp[i][j]+mod) % mod;
            }
        }
        return (int) dp[n][k];
    }
	/**
	 * describe:用动态规划 
	 * 2018年9月22日 下午3:01:02
	 */
	public int kInversePairs1(int n, int k) {
        int dp[][]=new int[n][k+1];
        dp[0][0]=1;
        for(int i=1;i<n;++i) {
        	for(int j=0;j<=k&&j<=i;++j) {
        		for(int z=0;z<=j;++z) {
        			dp[i][j]+=dp[i-1][z];
        		}
        	}
        }
        return dp[n-1][k];
    }
}
